package leetcode_600;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import helpclass.TreeNode;

/**
 *@author 周杨
 *MostFrequentSubtreeSum_508 一棵树的所有子树值总和的出现最频繁的数
 *describe:遍历map 用值进行排序 AC 18%
 *2018年9月6日 上午11:43:45
 */
public class MostFrequentSubtreeSum_508 {
	
	public static void main(String[] args) {
		MostFrequentSubtreeSum_508 test=new MostFrequentSubtreeSum_508();
		TreeNode root=new TreeNode(5);
		root.left=new TreeNode(2);
		root.right=new TreeNode(-5);
		test.findFrequentTreeSum(root);
	}
	Map<Integer,Integer> map;
	public int[] findFrequentTreeSum(TreeNode root) {
		if(root==null)
			return new int[] {};
        this.map=new TreeMap<Integer,Integer>();
        help(root);
        List<Map.Entry<Integer, Integer>> list
        =new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());//对map的值进行排序
        Collections.sort(list,new Comparator<Map.Entry<Integer, Integer>>() {

			@Override
			public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
				return o2.getValue().compareTo(o1.getValue());
			}
		});
        int top=list.get(0).getValue();
        int size=0;
        for(Map.Entry<Integer, Integer> entry:list) {
        	if(entry.getValue()!=top)
        		break;
        	++size;
        }
        int [] res=new int[size];
        for(int i=0;i<size;++i)
        	res[i]=list.get(i).getKey();
        return res;
        
    }
	
	
	public int help(TreeNode root) {
		if(root==null)
			return 0;
		int total= root.val+help(root.left)+help(root.right);
		if(map.containsKey(total))
			map.put(total, map.get(total)+1);
		else
			map.put(total, 1);
		return total;
	}
}
